﻿function EP() {
	this.parent = null
	this.evaluation = 0
	this.movement = 0
	this.value = null
}

var opened = []
var closed = []
var dim = 4
var target = []
for (var i = 0; i < dim * dim - 1; i++)
	target.push(i + 1)
target.push(0)




var dir = []
if (process.platform !== 'win32')

	dir = [' ', '←', '→', '↑', '↓']
else
	dir = ['　', '←', '→', '↑', '↓']

function avaliable(value) {
	var s1 = 0, s2 = 0
	for (var i = 0; i < dim * dim; i++)
		for (var j = 0; j < i; j++) {
			if (value[i] > value[j] && value[j] != 0)
				s1++
			if (target[i] > target[j] && target[j] != 0)
				s2++

		}
	return (s1 + s2) % 2 == 0
}

function check(value) {
	var sum = 0
	for (var i = 0; i < dim * dim; i++) {
		if (value[i] !== target[i])
			sum++
	}
	return sum
}

function init(value) {
	var maxdig = getMaxDigit(value)
	console.log('source')
	for (var i = 0; i < dim; i++) {
		var tmp = []
		for (var j = 0; j < dim; j++) {
			tmp.push(formatNum(value[i * dim + j], maxdig))
		}
		var str = tmp.join(' , ')
		str = '[ ' + str + ' ]'
		console.log(str)
	}
	console.log()
	maxdig = getMaxDigit(value)
	console.log('target')
	for (var i = 0; i < dim; i++) {
		var tmp = []
		for (var j = 0; j < dim; j++) {
			tmp.push(formatNum(target[i * dim + j], maxdig))
		}
		var str = tmp.join(' , ')
		str = '[ ' + str + ' ]'
		console.log(str)
	}
	console.log()
	if (dim % 2 === 1 && !avaliable(value)) {
		console.log('exactly no answer!!!')
		return false
	} else {
		opened = []
		closed = []
		var ep = new EP()
		ep.value = value
		opened.push(ep)
		return true

	}
}

function findZero(value) {
	for (var i = 0; i < value.length; i++) {
		if (value[i] === 0) {
			return i
		}
	}
	return -1
}

EP.prototype.findChildren = function () {
	var children = []
	var z = findZero(this.value)
	if (z !== -1) {
		var x = Math.floor(z / dim)
		var y = z % dim
		if (y > 0) {//左移
			extend(this, x, y, children, 1)
		}
		if (y < dim - 1) {//右移
			extend(this, x, y, children, 2)
		}
		if (x > 0) {//下移
			extend(this, x, y, children, 3)
		}
		if (x < dim - 1) {//上移
			extend(this, x, y, children, 4)
		}

	}
	return children

}

function extend(ep, x, y, children, mov) {
	var v = premove(ep.value, x, y, mov)
	if (notInClosed(v)) {
		var idx = findInOpened(v)
		var h = difference(v)
		if (-1 == idx) {
			var child = new EP()
			child.parent = ep
			child.movement = mov
			child.value = v
			child.evaluation = ep.evaluation + h
			children.push(child)

		} else {
			var exist = opened[idx]
			var eva = ep.evaluation + h
			if (eva < exist.evaluation) {
				exist.evaluation = eva
				exist.parent = ep
				exist.movement = mov

			}

		}
	}
}
function premove(value, x, y, mov) {
	var temp = []
	var t = 0
	for (var i = 0; i < value.length; i++) {
		temp.push(value[i])
	}
	switch (mov) {
		case 1:
			t = temp[x * dim + y - 1]
			temp[x * dim + y - 1] = temp[x * dim + y]
			temp[x * dim + y] = t
			break
		case 2:
			t = temp[x * dim + y + 1]
			temp[x * dim + y + 1] = temp[x * dim + y]
			temp[x * dim + y] = t

			break
		case 3:
			t = temp[(x - 1) * dim + y]
			temp[(x - 1) * dim + y] = temp[x * dim + y]
			temp[x * dim + y] = t

			break
		case 4:
			t = temp[(x + 1) * dim + y]
			temp[(x + 1) * dim + y] = temp[x * dim + y]
			temp[x * dim + y] = t

			break
	}
	return temp
}

function difference(value) {
	var sum = 0
	for (var i = 0; i < dim * dim; i++) {
		if (value[i] !== target[i])
			sum++
	}
	return sum
}

function calc() {
	var b = false
	var finalep = null
	while (opened.length > 0) {
		var ep = opened.shift()
		// console.log(ep.movement, ep.value)
		if (check(ep.value) === 0) {
			b = true
			finalep = ep
			break
		}
		closed.push(ep)
		var children = ep.findChildren()
		for (var i = 0; i < children.length; i++)
			opened.push(children[i])
		sortOpened()
	}
	if (b) {
		var ans = []
		while (finalep.parent !== null) {
			ans.push(finalep)
			finalep = finalep.parent
		}
		console.log('ok', ans.length)
		while (ans.length > 0) {
			var item = ans.pop()
			var maxdig = getMaxDigit(item.value)
			for (var i = 0; i < dim; i++) {
				var tmp = []
				for (var j = 0; j < dim; j++) {
					tmp.push(formatNum(item.value[i * dim + j], maxdig))
				}
				var str = tmp.join(' , ')
				str = ' [ ' + str + ' ] '

				console.log(dir[i == 0 ? item.movement : 0], str)

			}
			console.log()
		}
	} else {
		console.log('failed')
	}
}
function sortOpened() {
	opened.sort(function (a, b) {
		return a.evaluation - b.evaluation
	})

}
function vequal(v1, v2) {
	for (var i = 0; i < dim * dim; i++) {
		if (v1[i] !== v2[i])
			return false
	}
	return true
}
function notInClosed(epv) {
	for (var i = 0; i < closed.length; i++) {
		if (vequal(closed[i].value, epv))
			return false
	}
	return true
}
function findInOpened(epv) {
	for (var i = 0; i < opened.length; i++) {
		if (vequal(opened[i].value, epv))
			return i
	}
	return -1
}
function move(value) {
	var ret = []
	for (var i = 0; i < dim * dim; i++) {
		ret.push(value[i])
	}
	var z = findZero(value)
	var x = Math.floor(z / dim)
	var y = z % dim
	var m = []
	if (y > 0) {//左移
		m.push(1)
	}
	if (y < dim - 1) {//右移
		m.push(2)
	}
	if (x > 0) {//下移
		m.push(3)
	}
	if (x < dim - 1) {//上移
		m.push(4)
	}
	var r = m[Math.floor(Math.random() * m.length)]
	var t = 0
	switch (r) {
		case 1:
			t = ret[x * dim + y - 1]
			ret[x * dim + y - 1] = ret[x * dim + y]
			ret[x * dim + y] = t
			break
		case 2:
			t = ret[x * dim + y + 1]
			ret[x * dim + y + 1] = ret[x * dim + y]
			ret[x * dim + y] = t

			break
		case 3:
			t = ret[(x - 1) * dim + y]
			ret[(x - 1) * dim + y] = ret[x * dim + y]
			ret[x * dim + y] = t

			break
		case 4:
			t = ret[(x + 1) * dim + y]
			ret[(x + 1) * dim + y] = ret[x * dim + y]
			ret[x * dim + y] = t

			break
	}
	return ret
}

function difference(value) {
	var sum = 0
	for (var i = 0; i < dim * dim; i++) {
		if (value[i] !== target[i])
			sum++
	}
	return sum
}
function randomMove() {
	var ran = Math.floor(Math.random() * 100)
	v = []
	for (var i = 0; i < dim * dim; i++) {
		v.push(target[i])
	}
	for (var i = 0; i < ran; i++) {
		v = move(v);
	}
	return v
}

function getDigit(num) {
	var ret = 0
	if (num == 0) return 1
	while (num != 0) {
		ret++
		num = Math.floor(num / 10)
	}
	return ret
}

function formatNum(num, digit) {
	var dig = getDigit(num)
	var str = num.toString()
	var ret = ''
	for (var i = 0; i < digit - dig; i++) {
		ret += ' '
	}
	ret += str
	return ret
}
function getMaxDigit(value) {
	var ret = 0
	for (var i = 0; i < value.length; i++) {
		var d = getDigit(value[i])
		if (d > ret) {
			ret = d
		}
	}
	return ret
}

game = randomMove()
// game = [14, 13, 8, 15,
// 	2, 11, 12, 4,
// 	0, 5, 7, 10,
// 	3, 6, 1, 9]
if (init(game))
	calc()